from itertools import permutations
import numpy as np


def permute_path(path):
    return list(permutations(path))


def get_distance_city(point_position, index, logistics_center_position=None):
    distance = []
    if logistics_center_position == None:
        center_point_x = point_position[index - 1][0]
        center_point_y = point_position[index - 1][1]
        for i in range(len(point_position)):
            center_point_to_other_point = ((center_point_x - point_position[i][0]) ** 2 + (
                center_point_y - point_position[i][1]) ** 2) ** (1/2)
            str_index_format = '{0}->{1}'.format(index, i + 1)
            format_distance = (str_index_format, center_point_to_other_point)
            distance.append(format_distance)
    else:
        for i in range(len(point_position)):
            logistics_center_point_to_city = ((logistics_center_position[0] - point_position[i][0]) ** 2 + (
                logistics_center_position[1] - point_position[i][1]) ** 2) ** (1/2)
            str_index_format = '0->{0}'.format(i + 1)
            format_distance = (
                str_index_format, logistics_center_point_to_city)
            distance.append(format_distance)
    return distance


def split_path(path):
    split_path = []
    paths = []
    for i in range(len(path) + 1):
        if i == len(path) or (i != 0 and path[i] == 'new car'):
            paths.append(split_path)
            split_path = []
        elif path[i] != 'new car':
            split_path.append(path[i])
    return paths


def get_path_distance(path):
    # 初始化城市坐标
    points_position = [[12.8, 8.5], [18.4, 3.4], [15.4, 16.6], [18.9, 15.2], [15.5, 11.6], [3.9, 10.6], [10.6, 7.6], [8.6, 8.4], [12.5, 2.1], [
        13.8, 5.2], [6.7, 16.9], [14.8, 2.6], [1.8, 8.7], [17.1, 11], [7.4, 1],  [0.2, 2.8], [11.9, 19.8], [13.2, 15.1], [6.4, 5.6], [9.6, 14.8]]
    # 初始化各个城市需求量
    cities_need_goods = [0.1, 0.4, 1.2, 1.5, 0.8, 1.3, 1.7, 0.6,
                         1.2, 0.4, 0.9, 1.3, 1.3, 1.9, 1.7, 1.1, 1.5, 1.6, 1.7, 1.5]
    cities_distance = []
    # 获得城市之间的距离
    for i in range(1, 21):
        cities_distance.append(get_distance_city(points_position, i))
    # 定义物流中心的坐标
    logistics_center_position = [14.2, 13.1]
    logistics_center_to_cities_distance = get_distance_city(
        points_position, 0, logistics_center_position)
    distance = 0
    for i in range(len(path)):
        if i == 0:
            distance += logistics_center_to_cities_distance[path[i] - 1][1]
        else:
            current_city = path[i - 1]
            to_city = path[i]
            distance += cities_distance[current_city - 1][to_city - 1][1]
    distance += logistics_center_to_cities_distance[path[len(path) - 1] - 1][1]
    return distance


def opt_path(path):
    paths = split_path(path)
    min_path_distance = []
    min_paths = []
    for sub_path in paths:
        perm_path = permute_path(sub_path)
        min_distance = 9999
        for sub_perm_path in perm_path:
            sub_perm_path = list(sub_perm_path)
            distance = get_path_distance(sub_perm_path)
            if distance < min_distance:
                min_distance = distance
                min_path = sub_perm_path
        min_path_distance.append(min_distance)
        min_paths.append(min_path)
    return np.sum(min_path_distance), min_paths
